

//package leetcode.Fiftyone_to_One_hundred;
//
//import java.util.Stack;
//
///**
// * 柱状图中最大的矩形
// * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
// */
//public class Test84 {
//
//    public static int largestRectangleArea2(int[] heights) {
//        if (heights.length == 1)
//            return heights[0];
//
//        int maxArea = 0;
//        int left = 0;
//        int right = 0;
//        int weight = 0;
//        for (int i = 0; i < heights.length; i++) {
//            // 找到左边第一个小于当前柱子的边
//            for (int j = i - 1; j >= 0; j--) {
//                if (heights[j] < heights[i]) {
//                    left = j;
//                    break;
//                } else if (heights[j] == heights[i]) {
//                    left = j;
//                    continue;
//                } else {
//                    left = j;
//                    continue;
//                }
//            }
//            // 找到右边第一个小于当前柱子的边
//            for (int n = i + 1; n < heights.length; n++) {
//                if (heights[n] < heights[i]) {
//                    right = n;
//                    break;
//                } else if (heights[n] == heights[i]) {
//                    right = n;
//                    continue;
//                } else {
//                    right = n;
//                    continue;
//                }
//            }
//            if (left == 0) {
//                if (heights[left] > heights[right])
//                    weight = right;
//                else if (heights[left] < heights[right])
//                    weight = right-left;
//                else
//                    weight = right + 1;
//            } else if (right == heights.length - 1) {
////                if (heights[left] < heights[right])
////                    weight =
////                else
//                    weight = right - left + 1;
//            } else {
//                weight = right - left - 1;
//            }
//            maxArea = Math.max(maxArea, heights[i] * weight);
//        }
//        return maxArea;
//    }
//
//
//
//
//
//    public static int largestRectangleArea(int[] heights) {
//        Stack<Integer> stack = new Stack<>();
//        int maxArea = 0;
//        for (int i = 0; i < heights.length; i++) {
//            if (stack.isEmpty() || stack.peek() < i) {
//                stack.push(i);
//            } else {
//                while (stack.peek() > i) {
//                    int top = stack.pop();
//                    maxArea = Math.max(maxArea, heights[i] * (top-1-1));
//                }
//            }
//            stack.push(i);
//        }
////        while (stack.size() > 0) {
////            int top = stack.pop();
////            maxArea = Math.max(maxArea, heights[] * (top-1-1));
////        }
//        return maxArea;
//    }
//
//    public static void main(String[] args) {
////        int[] a = {2,1,5,6,2,3};
////        int[] a = {2,4};
////        int[] a = {4,2};
//        int[] a = {2,3};
////        int[] a = {2};
////        int[] a = {1, 1};
//        System.out.println(largestRectangleArea(a));
//    }
//}
